package com.hy.prefix_add;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:二维区域和检索 - 矩阵不可变
 * author: Mr.Du
 * Date: 2023/9/27
 * Time: 11:18
 */
public class PrefixAdd2DTemplate {
    int[][] res;
    public PrefixAdd2DTemplate(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        res = new int[m + 1][n + 1];
        for(int i = 1;i < m + 1;i++){
            for(int j = 1;j < n + 1;j++){
                res[i][j] = res[i - 1][j] + res[i][j - 1] + matrix[i - 1][j - 1] - res[i - 1][j - 1];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        return res[row2+1][col2+1] - res[row1][col2+1] - res[row2 + 1][col1] + res[row1][col1];
    }
}
